package leetcode.method.dynamic_programming;

import java.util.Arrays;

/**
 * 乘法太多浪费计算时间
 */
public class Program64Office {

    public Program64Office() {
    }

    private int[][] memo;
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int columns = grid[0].length;
        this.memo = new int[rows][columns];
        for(int[] array: memo){
            Arrays.fill(array,201);
        }
        memo[0][0] = grid[0][0];
        return dp(grid,rows-1,columns-1);
    }

    private int dp(int[][] grid,int r,int c){
        if(r<0 || c<0){
            return 201;
        }
        if(memo[r][c]!=201){
            return memo[r][c];
        }
        int res = 0;
        res = Math.min(
                dp(grid,r-1,c),
                dp(grid,r,c-1)
        )+grid[r][c];

        memo[r][c] = res;

        return memo[r][c];
    }

    public static void main(String[] args) {
        Program64Office myStack = new Program64Office();
        int[][] grid = {
                {1,3,1}
                ,{1,5,1}
                ,{4,2,1}
        };
        System.out.println(myStack.minPathSum(grid));
        int[][] grid1 = {
                {1,2,3}
                ,{4,5,6}
        };
        System.out.println(myStack.minPathSum(grid1));
    }
}
